package LeetCode.leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * 电话号码的字母组合
 * BFS 广度优先搜索算法
 * @author: leiwenkang02@meituan.com
 * @date: 2018/9/21
 * @time: 11:20
 */
public class Test17电话号码的字母组合 {
    public static void main(String[] args) {
        List<String> result = letterCombinations("23");
        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i));
        }
    }
    public static List<String> letterCombinations(String digits) {
        LinkedList<String> result = new LinkedList<String>();
        if (digits.isEmpty()) {
            return result;
        }
        String[] mapping = new String[]{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        result.add("");
        for (int i = 0; i < digits.length(); i++) {
            int num = Character.getNumericValue(digits.charAt(i));
            while (result.peek().length() == i) {
                String t = result.remove();
                for (char s : mapping[num].toCharArray()) {
                    result.add(t + s);
                }
            }
        }
        return result;
    }
}
